package com.echo.boot.structure.tree;

import com.echo.boot.pojo.User;
import com.echo.boot.structure.tree.binarytree.AVLTree;
import com.echo.boot.structure.tree.binarytree.BinarySearchTree;
import com.echo.boot.structure.tree.binarytree.RedBlackTree;
import com.echo.boot.structure.tree.printer.BinaryTrees;

import java.util.Comparator;

/**
 * Created with IntelliJ IDEA
 * Created By CQ
 * Date: 2020/5/9
 * Time: 18:25
 *
 * @author Administrator
 */
public class Main {
    public static void main(String[] args) {
        // 作业。。。递归加迭代
        // 二叉树反转
        // 前序遍历
        // 中序遍历
        // 后序遍历
        // 层次遍历
        // 二叉树的最大深度
        // 二叉树的反转
        // 已知前中,求后序
        // 已知后中,求前序
//        binarySearchTreeTest1();
//        binarySearchTreeTest2();
//
//        treeHeight1();
//
//        treeHeight2();
        AVLTreeTest();
//        redBlackTreeTest();

//        for (int binCount = 0; ; ++binCount) {
//            if (binCount >= 8 - 1) // -1 for 1st
//            {
//                System.out.println(binCount);
//                break;
//            }
//        }


    }


    static void binarySearchTreeTest1() {
//        Integer[] arr = {7, 4, 2, 1, 3, 5, 9, 8, 11, 10, 12};
        Integer[] arr = {7, 4, 2, 1, 3, 5, 9, 8, 11, 12};
        BinarySearchTree<Integer> tree = new BinarySearchTree<>();
        for (Integer integer : arr) {
            tree.add(integer);
        }
        BinaryTrees.print(tree);
        tree.remove(9);
        System.out.println();
        BinaryTrees.print(tree);
//        System.out.println();
//        tree.preloaderTraversal(new Visitor<Integer>() {
//            @Override
//            public boolean visit(Integer element) {
//                System.out.print(element + ", ");
//                return false;
//            }
//        });
//        System.out.println();
//        tree.inorderTraversal(new Visitor<Integer>() {
//            @Override
//            public boolean visit(Integer element) {
//                System.out.print(element + ", ");
//                return false;
//            }
//        });
//        System.out.println();
//        tree.postOrderTraversal(new Visitor<Integer>() {
//            @Override
//            public boolean visit(Integer element) {
//                System.out.print(element + ", ");
//                return false;
//            }
//        });


    }

    static void binarySearchTreeTest2() {
        BinarySearchTree<User> tree = new BinarySearchTree<>(new Comparator<User>() {
            @Override
            public int compare(User o1, User o2) {
                return o1.getAge() - o2.getAge();
            }
        });
        Integer[] arr = {7, 4, 9, 2, 5, 8, 11, 3};
//        for (int i = 0; i < arr.length; i++) {
//            tree.add(new User(arr[i]));
//        }
//        BinaryTrees.print(tree);
//        System.out.println();
    }

    static void treeHight1() {
        BinarySearchTree<Integer> tree = new BinarySearchTree<>();
        for (int i = 0; i < 6; i++) {
            tree.add((int) (Math.random() * 100));
        }
        BinaryTrees.print(tree);
        System.out.println();
        System.out.println(tree.height());
    }

    static void treeHight2() {
        BinarySearchTree<Integer> tree = new BinarySearchTree<>();
        for (int i = 0; i < 6; i++) {
            tree.add((int) (Math.random() * 100));
        }
        BinaryTrees.print(tree);
        System.out.println();
        System.out.println(tree.treeHeight());
    }

    static void AVLTreeTest() {
        Integer date[] = new Integer[]{
                77, 43, 9, 49, 72, 10, 26, 42, 12, 93, 76, 46, 17, 7, 37, 48, 88, 70, 60
        };
        AVLTree<Integer> avl = new AVLTree<>();
        for (Integer integer : date) {
            avl.add(integer);
            System.out.println("添加【" + integer + "】");
            BinaryTrees.println(avl);
            System.out.println("----------------------------------------------------------------------------------");
        }

        for (Integer integer : date) {
            avl.remove(integer);
            System.out.println("删除【" + integer + "】");
            BinaryTrees.println(avl);
            System.out.println("----------------------------------------------------------------------------------");
        }
    }

    static void redBlackTreeTest() {
        Integer date[] = new Integer[]{
                77, 43, 9, 49, 72, 10, 26, 42, 12, 93, 76, 46, 17, 7, 37, 48, 88, 70, 60
        };
        RedBlackTree<Integer> tree = new RedBlackTree<>();
        for (Integer integer : date) {
            System.out.println("添加【" + integer + "】");
            tree.add(integer);
            BinaryTrees.println(tree);
            System.out.println("----------------------------------------------------------------------------------");
        }


        for (Integer integer : date) {
            System.out.println("删除【" + integer + "】");
            tree.remove(integer);
            BinaryTrees.println(tree);
            System.out.println("----------------------------------------------------------------------------------");
        }
    }


}
